package tree;

import lombok.Setter;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树
 *
 * @author cooper
 * @date 2019-07-10
 */
public class BinaryTree {


    //根节点
    @Setter
    private Node root;

    public static BinaryTree buildTree(int[] array) {
        BinaryTree tree = new BinaryTree();
        tree.root = createNode(array, 0);
        return tree;
    }

    //构建树
    public static Node createNode(int[] array, int index) {
        if (array == null || index >= array.length) {
            return null;
        }
        Node n = new Node(array[index]);
        n.left = createNode(array, index * 2 + 1);
        n.right = createNode(array, index * 2 + 2);
        return n;
    }


    public BinaryTree add(int value) {
        add(new Node(value));
        return this;
    }

    /**
     * 增加节点
     *
     * @param node
     */
    public BinaryTree add(Node node) {
        if (root == null) {
            root = node;
            return this;
        }
        insert(root, node);
        afterInsert();
        return this;
    }

    private void insert(Node node, Node insert) {

        if (insert.value > node.value) {
            if (node.right != null) {
                insert(node.right, insert);
            } else {
                node.right = insert;
            }
        }
        if (insert.value < node.value) {
            if (node.left != null) {
                insert(node.left, insert);
            } else {
                node.left = insert;
            }
        }
    }

    protected void afterInsert() {

    }

    public void remove(Node node) {
        //TODO

        afterRemoved();
    }

    protected void afterRemoved() {
        //
    }

    /**
     * 前序遍历打印
     */
    public void print1() {
        printNode1(root);
    }

    public void print2() {
        printNode2(root);
    }

    public void print3() {
        printNode3(root);
    }

    /**
     * 前序遍历
     *
     * @param node
     */
    private void printNode1(Node node) {
        if (node != null) {
            System.out.print(node.value + "\t");
            printNode1(node.left);
            printNode1(node.right);
        }
    }

    /**
     * 中序遍历
     */
    private void printNode2(Node node) {
        if (node != null) {
            printNode2(node.left);
            System.out.print(node.value + "\t");
            printNode2(node.right);
        }
    }

    /**
     * 后序遍历
     */
    private void printNode3(Node node) {
        if (node != null) {
            printNode3(node.left);
            printNode3(node.right);
            System.out.print(node.value + "\t");
        }
    }

    /**
     * 前序遍历 非递归
     */
    public void print1_1() {

        Node cur = root;

        Stack<Node> stack = new Stack<>();

        while (true) {

            while (cur != null) {
                System.out.print(cur.value + "\t");
                stack.push(cur);
                cur = cur.left;
            }

            if (stack.empty()) {
                break;
            }
            cur = stack.pop();
            cur = cur.right;
        }
    }

    /**
     * 中序遍历 非递归
     */
    public void print2_1() {
        Node cur = root;

        Stack<Node> stack = new Stack<>();

        while (true) {

            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            if (stack.empty()) break;

            cur = stack.pop();
            System.out.print(cur.value + "\t");
            cur = cur.right;
        }
    }

    //前序遍历
    //中序遍历
    private void print1_2() {
        Node cur = root;
        Stack<Node> stack = new Stack<>();
        while (true) {

            while (cur != null) {
                stack.push(cur);
                System.out.printf("%d\t", cur.value);
                cur = cur.left;
            }
            if (stack.empty()) {
                break;
            }
            cur = stack.pop();
            cur = cur.right;
        }

    }

    //中序遍历
    private void print2_2(Node node) {
        Stack<Node> stack = new Stack<>();

        Node cur = node;

        while (true) {

            //将左节点入栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            if (stack.empty()) {
                break;
            }

            cur = stack.pop();
            System.out.println(cur.value);
            cur = cur.right;
        }

    }

    /**
     * 后序遍历 非递归
     */
    public void print3_1() {
        Node cur = root;
        Stack<Node> s1 = new Stack<>(), s2 = new Stack<>();
        Node p;
        s1.push(cur);

        while (!s1.empty()) {
            p = s1.pop();
            s2.push(p);
            if (p.left != null) {
                s1.push(p.left);
            }
            if (p.right != null) {
                s1.push(p.right);
            }
        }
        while (!s2.empty()) {
            System.out.printf("%d\t", s2.pop().value);
        }
    }

    /**
     * 深度优先遍历
     * 利用栈的原理，进行遍历
     * 非递归的前序-中序-后序遍历，均使用栈
     */
    public void dfsPrint() {

        Node cur = root;

        Stack<Node> nodes = new Stack<>();
        while (true) {

            while (cur != null) {
                nodes.push(cur);
                System.out.print(cur + "\t");
                cur = cur.left;
            }
            if (nodes.empty()) {
                break;
            }
            cur = nodes.pop();
            cur = cur.right;
        }


    }

    /**
     * 广度优先遍历
     */
    public void bfsPrint() {

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (queue.size() > 0) {
            Node node = queue.poll();
            System.out.print(node + "\t");
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {23, 43, 56, 7, 1, 3, 5, 77, 91};
        BinaryTree tree = buildTree(array);
        // 中序  77	7	91	43	1	23	3	56	5

        // 后序 77	91	7	1	43	3	5	56	23
        tree.print3();
        System.out.println();
        tree.print3_1();
    }

}
